#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
int N;
class route{
    public:
    int* stops;
    int length;
    route():stops(),length(0){
        this->stops = new int[N];
    };
    route(int start):stops(),length(0){
        this->stops = new int[N];
        this->stops[0]=start;
        this->length=0;//TODO：应该是0还是INT_MAX？
    }
    route(int start,int next,int length):stops(),length(length){
        this->stops = new int[N];
        this->stops[0]=start;
        this->stops[1]=next;
        this->length=length;
    }
    route(vector<int> stops,int length):stops(),length(length){
        this->stops = new int[N];
        for (int i=0;i<stops.size();i++)this->stops[i]=stops[i];
        this->length=length;
    };
};
int A2B_straight(int A,int k);
void fromAminRoad(int A,int distance[],int path[]){
    //route *routes=(route *)malloc(N*sizeof(route));//TODO:应该使用vector还是数组？->使用malloc
    bool *S=new bool[N];
    
    //int distance[N];
    for (int i=1;i<=N;i++){
        distance[i-1]= A2B_straight(A,i);
        S[i]=false;
        if (i!=A&&distance[i-1]<INT_MAX)path[i-1]=A;
        else path[i-1]=-1;
    } 
    
    S[A]=true;
    distance[A]=0;
    for (int i=0;i<N-1;i++){
        int min=INT_MAX;
        int stop=A;
        for (int j=1;j<=N;j++){
            if (!S[j-1]&&distance[j-1]<min){
                min=distance[j-1];
                stop=j;
            }
        }
        S[stop-1]=true;
        for (int k=1;k<=N;k++){
            int length2=A2B_straight(A,k);
            if (!S[k-1]&&length2<INT_MAX&&distance[stop-1]+length2<distance[k-1]){
                distance[k-1]=distance[stop-1]+length2;
                path[k-1]=stop;
            }
        }
    }
    
}
void the_shortest_path(int A,int B,int distance[],int path[]){
    int temp[N];
    int count=0;
    while (B!=A){
        temp[count]=B;
        B=path[B-1];
        count++;
    }

    while (count>0){
        cout<<temp[count-1];
        if (count!=1)cout<<" ";
        count--;
    }
    cout<<endl;
    return;
}